package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

//迭代:4ms 93%, 4.1MB 12%
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val > l2.Val {
		l1, l2 = l2, l1
	}
	head := l1
	for l1.Next != nil && l2 != nil {
		if l1.Next.Val < l2.Val {
			l1 = l1.Next
		} else {
			l1.Next = &ListNode{l2.Val, l1.Next}
			l1, l2 = l1.Next, l2.Next
		}
	}
	if l2 != nil {
		l1.Next = l2
	}
	return head
}

//递归:0ms 100%,4.1MB 34%
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	} else if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLists(l1, l2.Next)
		return l2
	}
}

func main() {
	fmt.Println(mergeTwoLists(nil, &ListNode{}))
	fmt.Println(mergeTwoLists1(nil, &ListNode{}))

}
